정수 계획법

완전 탐색은 정수 계획법 문제를 해결하는 가장 기본적이고 직관적인 방법이다. 이 방법은 문제의 모든 가능한 정수 해를 체계적으로 나열하고, 각 해가 제약 조건을 만족하는지 확인한 후, 그 중 목적 함수 값을 최적화하는 해를 선택한다. 특히 결정 변수가 0 또는 1의 값을 가지는 0-1 정수 계획법 문제나 변수의 범위가 매우 작은 경우에 적용 가능하다.

그러나 완전 탐색의 가장 큰 단점은 계산 복잡도이다. 변수의 수가 n개이고 각 변수가 가질 수 있는 정수 값의 경우의 수가 m가지라면, 탐색해야 할 해의 후보는 m^n개로 기하급수적으로 증가한다. 이는 조합 최적화 문제에서 흔히 마주치는 '조합의 폭발' 현상으로, 변수가 조금만 늘어나도 현실적인 시간 내에 문제를 풀기 어렵게 만든다.

따라서 완전 탐색은 문제의 규모가 매우 작을 때, 또는 다른 알고리즘의 정확성을 검증하는 벤치마크 용도로 제한적으로 사용된다. 대부분의 실용적인 정수 계획법 문제에서는 분기 한계법이나 절단 평면법과 같이 불필요한 해의 공간을 효과적으로 제거하는 알고리즘이, 또는 휴리스틱 알고리즘이 널리 활용된다.

분기 한정법은 정수 계획법 문제를 풀기 위한 가장 대표적인 완전 탐색 알고리즘이다. 이 방법은 선형 계획법의 심플렉스 방법을 기반으로 하여, 문제의 가능해 공간을 체계적으로 탐색하면서 최적의 정수 해를 찾아낸다. 기본 아이디어는 연속적인 최적화 문제의 해를 구한 후, 그 해가 정수 조건을 만족하지 않으면 해당 변수를 기준으로 문제를 두 개의 하위 문제(분기)로 나누고, 각 하위 문제에 대해 해의 하한 또는 상한(한계)을 계산하여 탐색할 필요가 없는 부분을 제거하는 것이다.

구체적인 과정은 다음과 같다. 먼저, 정수 조건을 무시하고 문제를 선형 계획법 문제로 풀어 실수 해를 구한다. 이 해가 모든 변수에서 정수 값을 가지면 그것이 최적해이다. 그렇지 않다면, 정수가 아닌 값을 가진 변수 중 하나를 선택하여, 그 변수가 특정 정수 값 이하인 경우와 이상인 경우로 문제를 두 개로 분할한다. 각 분할된 하위 문제는 다시 선형 계획법 문제가 되어 심플렉스 방법 등으로 풀린다.

이 과정에서 각 노드(하위 문제)에서 구한 선형 계획법 해의 목적 함수 값은 해당 노드에서 도달 가능한 최선의 정수 해에 대한 한계(대개 하한 for 최소화 문제) 역할을 한다. 현재까지 발견된 가장 좋은 정수 해의 값(현재 최적해)과 비교하여, 어떤 노드의 한계 값이 현재 최적해보다 나쁘다면, 그 노드와 그 하위 노드들은 더 이상 탐색할 필요가 없으므로 제거(한정)된다. 이렇게 분기와 한정을 반복하며 탐색 공간을 효과적으로 줄여 나간다.

분기 한정법은 조합 최적화 문제에 널리 적용되며, 외판원 문제나 배낭 문제 같은 고전적인 문제뿐만 아니라 실제 스케줄링이나 물류 네트워크 설계 문제를 푸는 소프트웨어의 핵심 엔진으로 사용된다. 이 방법은 이론적으로 최적해를 보장하지만, 문제의 규모가 커질수록 계산 시간이 급격히 증가할 수 있다는 단점이 있다.

절단 평면법은 정수 계획법 문제를 해결하는 대표적인 정확 알고리즘 중 하나이다. 이 방법은 문제의 정수성 제약을 일시적으로 완화한 선형 계획법 문제를 반복적으로 풀어나가며, 정수 최적해를 찾는 과정에서 필요할 때마다 새로운 선형 제약 조건을 추가하여 해 공간을 점차 좁혀나간다. 추가되는 이러한 제약 조건을 '절단 평면' 또는 단순히 '절단'이라고 부르며, 이는 현재의 선형 계획법 최적해가 정수가 아니라는 사실을 이용하여 해당 비정수해를 제외시키는 역할을 한다.

절단 평면법의 핵심은 각 반복에서 얻은 비정수 최적해를 분석하여, 해당 해를 배제하면서도 가능한 모든 정수 해는 보존하는 새로운 선형 부등식을 도출하는 것이다. 가장 잘 알려진 절단 평면법의 예로는 곰리 절단 평면법이 있다. 이 방법은 단체법의 최종 심플렉스 테이블을 분석하여, 기저 변수의 비정수 부분에서 직접 절단 평면을 생성하는 체계적인 방식을 제공한다.

절단 평면법은 단독으로 사용되기보다는 종종 분기 한정법과 결합된 분기 절단법의 형태로 활용된다. 분기 한정법은 문제를 부분 문제로 나누어 탐색하는 반면, 절단 평면법은 각 부분 문제의 선형 계획법 완화 문제를 더욱 강화하여 하한값을 개선한다. 이 두 방법을 함께 사용하면 탐색해야 할 부분 문제의 수를 줄이고 전반적인 계산 효율성을 높일 수 있다. 절단 평면법은 특히 조합 최적화 문제에서 강력한 하한을 제공하는 데 유용하다.

정수 계획법은 스케줄링 문제를 해결하는 데 매우 효과적으로 활용된다. 스케줄링은 제한된 자원과 시간 내에 작업이나 일정을 효율적으로 배치하는 문제로, 생산 계획, 프로젝트 관리, 인력 배치 등 다양한 분야에서 핵심적인 과제이다. 이러한 문제들은 대부분 작업의 시작 시간, 기계 할당, 인원 배치 등과 같은 결정 변수가 정수 값을 가져야 하기 때문에, 연속적인 해를 허용하는 선형 계획법만으로는 최적해를 구하기 어렵다.

대표적인 응용 사례로는 작업장 스케줄링이 있다. 여러 대의 기계에 여러 개의 작업을 할당하고, 각 작업의 처리 순서와 시간을 결정하여 총 완료 시간을 최소화하는 문제이다. 이때 각 작업이 특정 기계와 특정 시간 슬롯에 할당되는지를 나타내는 변수는 0 또는 1의 값을 가지는 이진 변수로 모델링된다. 또한, 항공사 일정 계획에서는 각 비행기의 운항 스케줄, 승무원 배정, 정비 일정 등을 동시에 고려하는 복잡한 정수 계획법 모델이 사용된다.

스케줄링 문제를 정수 계획법으로 공식화하면, 작업 간의 선후행 관계, 자원의 가용성, 작업의 마감 기한 등 다양한 제약 조건을 명시적으로 수식으로 표현할 수 있다. 이를 통해 분기 한계법이나 전문적인 솔버를 이용해 최적 또는 실용적인 해를 찾을 수 있다. 이는 단순한 규칙 기반의 스케줄링보다 훨씬 체계적이고 최적화된 결과를 도출하여, 생산성 향상과 비용 절감에 기여한다.

정수 계획법은 물류 및 공급망 관리 분야에서 복잡한 의사결정 문제를 모델링하고 최적화하는 데 핵심적으로 활용된다. 이 분야에서는 창고 위치 선정, 운송 경로 최적화, 재고 관리, 수요 예측 기반 생산 계획 등 다양한 요소들이 서로 얽혀 있으며, 이러한 결정들은 대부분 이산적인 값을 가진다. 예를 들어, 새로운 분배 센터를 몇 군데 지을지, 각 공장에서 각 소매점으로 얼마나 많은 화물을 보낼지, 또는 어떤 배송 차량을 어떤 경로에 할당할지 등의 문제는 정수 변수로 표현된다. 이러한 문제를 선형 계획법만으로 풀면 해가 분수가 나와 실행 불가능한 경우가 많기 때문에, 정수 값을 강제하는 제약 조건이 필수적이다.

대표적인 응용 사례로는 차량 경로 문제가 있다. 이 문제는 여러 대의 차량이 한 창고에서 출발하여 여러 고객 지점을 방문한 후 돌아올 때, 총 이동 거리나 비용을 최소화하는 경로를 찾는 것이다. 각 고객 지점은 정확히 한 번만 방문해야 하며, 차량의 용량 제약을 고려해야 한다. 이때 '차량 A가 고객 B를 방문하는가'와 같은 결정은 0 또는 1의 값을 가지는 변수로 모델링되며, 이는 0-1 정수 계획법의 전형적인 예이다. 또한 공장이나 창고의 입지 선정 문제에서는 특정 후보지에 시설을 건설할지 말지의 여부가 0-1 변수로, 해당 시설에서 처리하는 물량은 정수 변수로 표현되어 혼합 정수 계획법 모델이 구성된다.

물류 네트워크 설계와 같은 대규모 문제는 변수와 제약 조건의 수가 매우 많아 최적해를 찾는 데 상당한 계산 시간이 소요될 수 있다. 따라서 실무에서는 분기 한정법이나 절단 평면법 같은 정확한 해법 알고리즘과 더불어, 근사해를 빠르게 찾는 휴리스틱 알고리즘이 함께 사용되기도 한다. 이러한 최적화를 통해 기업은 운송 비용을 절감하고, 자원 활용도를 높이며, 전체 공급망의 효율성과 탄력성을 크게 향상시킬 수 있다. 결국 정수 계획법은 복잡한 물류 시스템을 체계적으로 분석하고 합리적인 의사결정을 지원하는 강력한 수학적 도구 역할을 한다.

통신 네트워크 설계와 운영은 정수 계획법의 주요 응용 분야 중 하나이다. 네트워크는 본질적으로 이산적인 요소들, 예를 들어 라우터나 스위치 같은 장비의 설치 여부, 광케이블이나 무선 링크의 경로 선택, 대역폭 할당 단위 등으로 구성되기 때문에, 이러한 문제들을 모델링하고 최적의 해를 찾는 데 정수 계획법이 적합하게 사용된다.

대표적인 응용 사례로는 네트워크 설계 문제가 있다. 이는 주어진 트래픽 수요와 서비스 수준 협약을 만족시키면서, 네트워크 장비 구매 비용과 링크 설치 비용을 최소화하는 토폴로지와 장비 배치를 결정하는 문제이다. 여기서 각 노드에 설치할 장비의 종류와 수, 노드 간에 설치할 링크의 용량과 유무는 모두 정수 변수로 표현된다. 또한, 통신 위성의 궤도 슬롯 할당이나 지상국 안테나의 빔 포인팅 스케줄링 문제도 정수 계획법으로 풀 수 있다.

라우팅과 자원 할당 문제에서도 정수 계획법이 활용된다. 예를 들어, 멀티캐스트 트리를 구성하거나 네트워크 코딩을 적용할 링크를 선택하는 문제, 제한된 스펙트럼 자원을 여러 셀이나 사용자에게 효율적으로 나누어 주는 문제 등이 있다. 5G나 차세대 네트워크에서 중요한 개념인 네트워크 슬라이싱은 물리적 인프라를 여러 개의 논리적 네트워크로 분할하는 기술로, 각 슬라이스에 가상 머신, 대역폭, 저장 장치 등의 자원을 정수 단위로 할당하는 최적화 문제를 포함한다.

배낭 문제는 정수 계획법과 조합 최적화에서 가장 잘 알려진 기초 문제 중 하나이다. 이 문제는 제한된 용량의 배낭에 여러 물건을 넣을 때, 각 물건의 가치와 무게가 주어졌을 때 배낭의 용량을 초과하지 않으면서 총 가치를 최대화하는 물건의 조합을 찾는 문제이다. 이는 자원이 제한된 상황에서 최적의 선택을 해야 하는 다양한 실제 문제를 모델링하는 데 사용된다.

배낭 문제는 일반적으로 0-1 정수 계획법 문제로 공식화된다. 각 물건을 배낭에 넣거나(1) 넣지 않거나(0) 하는 이진 결정 변수를 사용하며, 목적 함수는 물건들의 총 가치를 최대화하고, 제약 조건은 물건들의 총 무게가 배낭의 용량을 초과하지 않도록 하는 선형 제약이다. 이렇게 모델링된 문제는 선형 계획법의 특수한 형태인 정수 계획법 문제가 된다.

이 문제의 해법으로는 동적 계획법이나 분기 한정법과 같은 정확한 알고리즘이 널리 사용된다. 특히 동적 계획법은 무게 제한에 대해 가능한 모든 부분 문제를 해결하여 최적해를 보장한다. 그러나 물건의 수가 많아지면 문제의 복잡도가 급격히 증가하여, 휴리스틱 알고리즘이나 메타휴리스틱을 활용한 근사 해법이 실용적으로 사용되기도 한다.

배낭 문제는 단순한 모델이지만, 자원 할당, 예산 편성, 투자 포트폴리오 선택 등 다양한 분야에서 응용된다. 또한 이 문제는 NP-난해 문제로 분류되어, 계산 이론에서 문제의 난이도를 이해하는 데 중요한 역할을 한다. 배낭 문제를 변형한 다중 배낭 문제나 제한 없는 배낭 문제 등도 활발히 연구되는 주제이다.

외판원 문제는 조합 최적화 분야에서 가장 잘 알려진 문제 중 하나로, 정수 계획법의 대표적인 응용 사례이다. 이 문제는 여러 도시를 방문하는 외판원이 각 도시를 정확히 한 번씩만 방문하고 출발지로 돌아오는 최단 경로를 찾는 것이다. 각 도시 간 이동 거리나 비용이 주어졌을 때, 가능한 모든 경로 중 총 이동 거리나 비용을 최소화하는 해밀턴 순환을 찾는 것이 목표이다.

이 문제는 정수 계획법을 이용해 정식으로 모델링될 수 있다. 일반적으로 각 도시 간 경로의 사용 여부를 0 또는 1의 이진 변수로 정의하고, 모든 도시가 순환 경로에 포함되도록 하는 제약 조건을 선형 부등식으로 표현한다. 또한, 부분 순환을 방지하기 위한 추가적인 제약 조건(MTZ 제약 또는 흐름 제약 등)이 필요하다. 이렇게 구성된 혼합 정수 계획법 모델은 분기 한계법이나 절단 평면법 같은 기법으로 해결을 시도할 수 있다.

그러나 외판원 문제는 NP-난해 문제로 분류되며, 도시의 수가 증가함에 따라 가능한 경로의 수가 계승 함수로 폭발적으로 증가한다. 이 때문에 정수 계획법 기반의 정확한 해법으로는 대규모 문제를 푸는 데 한계가 있다. 이러한 이유로 실제 응용에서는 휴리스틱 알고리즘이나 메타휴리스틱 방법이 널리 사용된다. 대표적인 예로 가장 가까운 이웃 알고리즘이나 유전 알고리즘, 개미 집단 최적화 등이 있다.

외판원 문제는 이론적 중요성을 넘어 실용적인 가치도 매우 크다. 이 문제의 해법은 물류 및 배송 경로 최적화, 인쇄 회로 기판의 드릴링 경로 설계, DNA 시퀀싱, 그리고 기계 학습에서의 군집 분석 등 다양한 분야에 응용된다. 따라서 외판원 문제는 정수 계획법과 조합 최적화 연구의 핵심 동력이 되며, 효율적인 근사 해법을 개발하는 것은 여전히 활발한 연구 주제이다.